package lc.q201_250;

import lc.TreeNode;

import java.util.*;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 */
public class Q236 {

    Set<TreeNode> contains = new HashSet<>();

    private boolean contain(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        if (root == p || root == q || contains.contains(root)) {
            contains.add(root);
            return true;
        } else {
            if (root.left == null && root.right == null) {
                return false;
            }
            final boolean b = (contain(root.left, p, q)) ||
                    (contain(root.right, p, q));
            if (b) {
                contains.add(root);
            }
            return b;
        }

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 对二叉树的广度优先遍历
        // 对左子树和右子树查找是否存储p或者q，如果都包含，那说明root是最小的
        // 如果一个存在，一个不存在，则查询哪个存在的
        // 如果root恰好等于p，则说明root就是它
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        // 查找左子树是否存在
        final boolean leftContain = contain(root.left, p, q);
        final boolean rightContain = contain(root.right, p, q);
        if (leftContain && rightContain) {
            return root;
        } else if (leftContain) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }

}
